package 数据结构专栏.简单级别;

import java.util.*;

/**
 * @DESC 翻转一棵二叉树。
 * https://leetcode-cn.com/problems/invert-binary-tree/
 * <p>
 * 输入
 * 4
 * /   \
 * 2     7
 * / \   / \
 * 1   3 6   9
 * <p>
 * 4
 * /   \
 * 7     2
 * / \   / \
 * 9   6 3   1
 * @Author tzq
 * @Date 2020-03-27 20:45
 **/
public class _226_翻转二叉树 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode t1 = new TreeNode(2);
        TreeNode t2 = new TreeNode(7);
        TreeNode t3 = new TreeNode(1);
        TreeNode t4 = new TreeNode(3);
        TreeNode t5 = new TreeNode(6);
        TreeNode t6 = new TreeNode(9);
        root.left = t1;
        root.right = t2;
        t1.left = t3;
        t1.right = t4;
        t2.left = t5;
        t2.right = t6;

        System.out.println(printTree(root));
        System.out.println(printTree(invertTree(root)));

    }

    /**
     * 依然只看三个 终止条件，只看一层 返回什么
     * 我的解法， 大哭一场...
     *
     * @param root
     * @return
     */
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        if (root.left == null && root.right == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;

    }


    /**
     * 打印二叉树
     * https://blog.csdn.net/u013132035/article/details/80604718
     *
     * @param root
     * @return
     */
    public static List<Integer> printTree(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return Collections.emptyList();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currTree = queue.poll();
            if (currTree.left != null) {
                queue.offer(currTree.left);
            }
            if (currTree.right != null) {
                queue.offer(currTree.right);
            }
            list.add(currTree.val);
        }


        return list;
    }

}
